package com.sxt;
/**
 * 基于单向列表的实现类
 * 注意：单向列表必须牢牢抓住头列表，头节点列表不可以动  可以定义多一个可以移动的指针*/
public class MySinglyLinkedList<E> implements MyList<E>{
   /*内部类的总结：为了更好地隐藏。作用：当一些类型不具备通用性时
   * 或者是只能在某一个对象当中使用时，是这个对象所独有的*/
    //定义单向链表中的节点对象
    //因为要在类中节点象存放元素，元素是有类型的，所以定义泛型类型
    class Node<E>{
        //记录元素的成员变量  记录节点地址的成员变量（单向链表所以一个节点就足够）
        private E item;//存储元素
       private Node next;//存储节点地址 因为下一个节点的对象也是Node类型
        //构造方法，方便传递数据
       Node(E item,Node next){
           this.item=item;
           this.next=next;
       }

    }
    private Node head;//存放链表中的头节点
    private int size;//记录元素个数
    //添加元素
    @Override
    public void add(E element) {
        //创建节点
        Node<E> node = new Node<>(element, null);
        //尾节点  通过头找到尾
        Node tail = getTail();

        //节点挂接
        if (tail == null) {
            this.head = node;
        } else {
            tail.next = node;
        }
        //记录元素个数
        this.size++;
    }
    //找尾节点
    private Node getTail(){
        //头节点是否存在
        if(this.head == null){
            return null;
        }
        //查找尾节点
        Node node = this.head;//创建一个可以移运的节点
        while (true){
            //要在这n上面：node = node.next;  否则报空指针
            if(node.next == null) {
                break;
            }

            //通过当前节点的next，获取下一个节点
            node = node.next;//节点移动，指向下一个节点
        }
        return node;
    }
    //根据元素位置获取元素
    @Override
    public E get(int index) {
        //校检index的合法性  效检方法另写，不可以写在这里，因为只要是index都要用到
        this.checkIndex(index);
        //根据位置获取指定节点
        Node<E> node = this.getNode(index);
        //将该节点元素返回
        return node.item;

    }
    //对index 进行校检  抛出异常，不用返回值
    private void checkIndex(int index){
        if(!(index>=0 && index<this.size)){
            throw new IndexOutOfBoundsException("Index:"+index+"Size:"+this.size);
        }
    }
    /*根据位置获取节点  有返回值*/
    private Node getNode(int index){
        /*头节点列表不可以动  可以定义多一个可以移动的指针*/
        Node<E> node = this.head;
        for(int i=0;i<index;i++){
            node = node.next; //指针移动
        }
        return node;
    }
    //获取元素个数
    @Override
    public int size() {
        return this.size;
    }
    //根据元素位置删除元素
    @Override
    public E remove(int index) {
        //校检Index的合法性
        this.checkIndex(index);
        //根据位置找到该节点 对象
        Node<E> node = this.getNode(index);
        //获取该节点对象的 元素
        E item = node.item;
        //将该节点对象从单向链表中移除
        //如果头节点是被删除的节点，将头指针向下移一位节点为头节点
        if(this.head==node){
            this.head=node.next;
        }else {
            Node<E> temp = this.head;
            //当前节点的上一个节点
            for (int i=0;i<index-1;i++){
                temp = temp.next;
            }
            //被删除的节点的上一个节点指向被删除的节点的下一个节点
            temp.next = node.next;
        }
        //记录元素个数
        this.size--;
        //将该元素返回
        return item;
    }
    //
    public static void main(String[] args) {
        MySinglyLinkedList<String> mySinglyLinkedList = new MySinglyLinkedList<>();
        mySinglyLinkedList.add("a");
        mySinglyLinkedList.add("b");
        mySinglyLinkedList.add("c");
        mySinglyLinkedList.add("d");
        System.out.println(mySinglyLinkedList.size);
        System.out.println(mySinglyLinkedList.remove(0));
        for(int i=0;i< mySinglyLinkedList.size;i++){
            System.out.println(mySinglyLinkedList.get(i));
        }
    }
}
